import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @FileName Solution1387
 * @Description
 * @Author tong.zhou
 * @date 2024-12-22
 **/
public class Solution1387 {

    Map<Integer, Integer> numAndStepMap = new HashMap<>();

    private int getStep(int num){
        Integer resStep;
        resStep = numAndStepMap.get(num);
        if(resStep != null){
            return resStep;
        }
        if(num == 1) {
            resStep = 0;
        } else if(num % 2 == 0){
            resStep = 1 + getStep(num / 2);
        } else {
            resStep = 1 + getStep(num * 3 + 1);
        }
        numAndStepMap.put(num, resStep);
        return resStep;
    }

    private void add(PriorityQueue<int[]> priorityQueue, int[] arr, int k){
        priorityQueue.add(arr);
        while(priorityQueue.size() > k){
            priorityQueue.poll();
        }
    }

    public int getKth(int lo, int hi, int k) {
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(k,
                (a, b) -> {int result = Integer.compare(b[0], a[0]);
            if (result == 0) {
                // 如果第一个元素相同，再比较第二个元素
                result = Integer.compare(b[1], a[1]);
            }
            return result;});
        for (int i = lo; i <= hi; i++) {
            int resStep = getStep(i);
            add(priorityQueue, new int[]{resStep, i}, k);
        }
        return priorityQueue.poll()[1];
    }

    public static void main(String[] args) {
        Solution1387 s = new Solution1387();
        s.getKth(12,15,2);
    }
}
